import copy

class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nDict = {}
        for num in nums:
            if num not in nDict:
                nDict.update({num:0})
            nDict[num]+=1
        

        ret = []
        acc = []
        def find(nums):
            if len(nums)==0:
                ret.append(copy.copy(acc))
                return
            tmp = copy.copy(nums)
            for num in nums.keys():
                acc.append(num)
                if tmp[num]==1:
                    del tmp[num]
                    find(tmp)
                    tmp.update({num:1})
                else:
                    tmp[num]-=1
                    find(tmp)
                    tmp[num]+=1
                acc.pop()
        find(nDict)
        return ret

print(Solution().permuteUnique([1,1,2]))